/*
题目: 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
https://leetcode.cn/problems/subsets/
 */
public class Subsets {
    List<List<Integer>> res = new ArrayList<> ();

    public List<List<Integer>> subsets(int[] nums) {
        //回溯
        res.add(new ArrayList<> ());
        backTrack(nums, 0, new ArrayList<> ());
        return res;
    }

    private void backTrack(int[] nums, int index, List<Integer> path) {
        if (index >= nums.length) {
            return ;
        }

        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            res.add(new ArrayList<> (path));
            backTrack(nums, i + 1, path);
            path.remove(path.size() - 1);
        }
    }
}
